package code901_1000.code70_80;

/**
 * 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
 *
 * 输入：nums = [-4,-1,0,3,10]
 * 输出：[0,1,9,16,100]
 * 解释：平方后，数组变为 [16,1,0,9,100]
 * 排序后，数组变为 [0,1,9,16,100]
 *
 * 输入：nums = [-7,-3,2,3,11]
 * 输出：[4,9,9,49,121]
 *
 */
public class _977sortedSquares {

    /**
     * 思考：1：首先找到第一个非负数，将前面的复数全部转换为整数，插入到后续数组中，然后逐个进行平方
     *      2：首先找到第一个非负数，全部进行平方，将所有的复数平方重新插入到原数组中。
     *      综合考虑，第一个方案
     * @param nums
     * @return
     */
    public static int[] sortedSquares(int[] nums) {
        if(nums.length==1){
            nums[0] = nums[0]*nums[0];
            return nums;
        }
        // pos 表示第一个非负数的位置
        int pos = 0;
        for (int i = 0; i < nums.length; i++) {
            pos = i;
            if(nums[i]<0){
                continue;
            }else {
                break;
            }
        }
        // 统一预处理，重新排序数组
        if(pos == nums.length-1){
            int temp = nums[0];
            for (int i = 0; i < nums.length/2+1; i++) {
                temp = nums[i];
                nums[i] = nums[nums.length-i-1];
                nums[nums.length-i-1] = temp;
            }
        }else if(pos>0){
            int[] temp = new int[pos];
            //将负数转为正数
            for (int i = 0; i < temp.length; i++) {
                temp[i] = nums[temp.length-i-1]*(-1);
            }
            // 将负数重新插入到nums数组中。为合并两个有序数组问题
            int k = 0;
            int l = pos;
            // 此问题转换为合并两个有序数组
            // 第一个有序数组 temp ： 0-----------pos-1长度
            // 第二个有序数组 nums ： pos---------nums.length-1长度。总长度nums.length
            for (int i = 0; i < nums.length; i++) {
                if(k==pos)break;
                if(l == nums.length){
                    for (int j = 0; j < pos-k; j++) {
                        nums[k+l-1] = temp[k++];
                    }
                    break;
                }
                if(nums[l]>=temp[k]){
                    nums[i] = temp[k++];
                }else {
                    nums[i] = nums[l++];
                }
            }
        }

        // 统一进行平方
        for (int i = 0; i < nums.length; i++) {
            nums[i] *= nums[i];
        }
        return nums;
    }

    public static void main(String[] args) {
        for (Integer temp :
                sortedSquares(new int[]{-2,-1,3})) {
            System.out.println(temp);
        }
    }

}
